package cn.zifangsky.tree.binarytree.questions;

import java.util.Arrays;

import org.junit.Test;

import cn.zifangsky.queue.LinkQueue;
import cn.zifangsky.tree.binarytree.BinaryTreeNode;

/**
 * 设计一个算法：可以根据给定的前序遍历和中序遍历序列来构建二叉树
 * @author zifangsky
 *
 */
public class Question16 {

	/**
	 * 根据前序遍历和中序遍历序列构建二叉树
	 * 思路：
	 * 		1. 使用前序遍历序列中的第一个节点构成这个二叉树的根节点——root
	 * 		2. 接着从中序遍历序列中找到这个数字所在的位置——inSize，该位置左边的所有数字为root的左子树，该位置右边的所有数字为root的右子树
	 *      3. 构建root的左子树：前序遍历序列中从第二个数字开始的inSize个节点作为新的前序遍历序列；中序遍历中的前inSize个数字作为新的中序遍历序列
	 *      4. 构建root的右子树：前序遍历序列中位置inSize之后的所有数字作为新的前序遍历序列；中序遍历中位置inSize之后的所有数字作为新的中序遍历序列
	 *      5. 上述过程反复递归，直到生成完整的二叉树
	 *     
	 * @时间复杂度 O(n)
	 * @param preOrderList 前序遍历序列
	 * @param inOrderList 中序遍历序列
	 * @param root
	 * @return 构建之后的二叉树的根节点
	 */
	public BinaryTreeNode<Integer> buildTree(int[] preOrderList,int[] inOrderList){
		if(preOrderList.length <=0 || inOrderList.length <= 0){
			return null;
		}
		
		//1 构建根节点
		BinaryTreeNode<Integer> root = new BinaryTreeNode<Integer>(preOrderList[0]);
		
		//2 中序遍历序列中找到 preOrderList[0] 这个数字所在的位置——inSize
		int inSize = -1;
		for(int i=0;i<inOrderList.length;i++){
			if(inOrderList[i] == preOrderList[0]){
				inSize = i;
				break;
			}
		}
		
		if(inSize == -1){
			throw new RuntimeException("前、中序遍历序列不匹配");
		}
		
		//3 preOrderList[0]不在中序遍历序列的第一位，则说明存在左子树
		if(inSize > 0){
			//新的左子树的前序遍历序列
			int[] subLeftPreOrderList = Arrays.copyOfRange(preOrderList, 1 ,inSize+1);
			//新的左子树的中序遍历序列
			int[] subLeftInOrderList = Arrays.copyOfRange(inOrderList, 0 ,inSize);
			
			//生成root的左孩子节点
			BinaryTreeNode<Integer> leftChildTree = buildTree(subLeftPreOrderList,subLeftInOrderList);
			root.setLeft(leftChildTree);
		}
		
		//4 preOrderList[0]不在中序遍历序列的最后一位，则说明存在右子树
		if(inSize < preOrderList.length - 1){
			//新的右子树的前序遍历序列
			int[] subRightPreOrderList = Arrays.copyOfRange(preOrderList, inSize+1 ,preOrderList.length);
			//新的右子树的中序遍历序列
			int[] subRightInOrderList = Arrays.copyOfRange(inOrderList, inSize+1 ,preOrderList.length);
			
			//生成root的右孩子节点
			BinaryTreeNode<Integer> rightChildTree = buildTree(subRightPreOrderList,subRightInOrderList);
			root.setRight(rightChildTree);
		}
		
		return root;
	}

	/**
	 * 层次遍历：使用队列辅助操作
	 * @时间复杂度 O(n)
	 * @param root
	 */
	private void levelOrder(BinaryTreeNode<Integer> root){
		LinkQueue<BinaryTreeNode<Integer>> queue = new LinkQueue<>();
		if(root != null){
			queue.push(root);
		}
		
		while (!queue.isEmpty()) {
			BinaryTreeNode<Integer> temp = queue.pop();
			System.out.print(temp.getData() + " ");
			
			if(temp.getLeft() != null){
				queue.push(temp.getLeft());
			}
			if(temp.getRight() != null){
				queue.push(temp.getRight());
			}
		}
	
	}

	/**
	 * 测试用例
	 */
	@Test
	public void testMethods(){
		/**
		 * 供测试使用的二叉树
		 *     1
		 *   2    3
		 * 4  5  6  7
		 *   8 9  
		 */
		int[] preOrderList = {1,2,4,5,8,9,3,6,7};
		int[] inOrderList = {4,2,8,5,9,1,6,3,7};
		
		BinaryTreeNode<Integer> root = buildTree(preOrderList,inOrderList);
		//层次遍历
		levelOrder(root);
	}

}
